package cn.ly.quicksort;

import cn.ly.util.ArithmeticTool;

public class ArrayIns {	
	private long[] theArray;
	private int nElems;
	
	public ArrayIns(int size){
		theArray = new long[size];
		nElems = 0;
	}
	
	public void insert(long value){
		theArray[nElems] = value;
		nElems++;
	}
	
	public int size(){
		return nElems;
	}
	
	public void display(){
		for(int i=0; i<nElems; i++){
			System.out.print(theArray[i] + " ");
		}
		System.out.println();
	}
	
	public void quickSort(){
		recQuickSort(0,nElems-1);
	}
	
	public void recQuickSort(int left,int right){
		if(left < right){
			long pivot = theArray[right];
			int partition = part(left,right,pivot);
			recQuickSort(left,partition-1);
			recQuickSort(partition,right);
		}else{
			//insertSort();
		}
	}
	
	private int part(int left,int right,long piovt){
		int i = left;
		int j = right;
		while(true){
			//1、从左向右找大于 pivot的元素
			while(i < right && theArray[i] < piovt){
				i++;
			}
			//2、从右向左找小于pivot的元素
			while(j > left && theArray[j] > piovt){
				j--;
			}
			//3、判断左侧指针i 是否 大于等于  右边指针 j
			if(i >= j){
				break;//4、如果true，则退出
			}
			swap(i,j);//5、否则就交换这两个元素
		}
		return i;
	}
	
	//交换数据元素
	private void swap(int dex1,int dex2){
		long temp = theArray[dex1];
		theArray[dex1] = theArray[dex2];
		theArray[dex2] = temp;
	}
	
	public static void main(String[] args) {
		ArrayIns arr = new ArrayIns(100);
		for(int i=0; i<10; i++){
			arr.insert(ArithmeticTool.getIntRandom0to100());
		}
		arr.display();
		arr.quickSort();
		arr.display();
	}

}
